1. Field of the Invention
This invention is related to random number generator circuits and pseudo-random number generator circuits and, more particularly, to a random number generator circuit for generating a random replacement way for a cache.
2. Description of the Related Art
Random number generator circuits have a variety of uses in various circuits, such as integrated circuits. For example, random number generator circuits may be used, in a set associative cache, to select a random replacement way from which to evict data in order to store a newly fetched cache line (in response to a cache miss). A random number generator circuit could be addressable via instructions in a processor to provide a random number for software use. For example, various games and other applications may benefit from being able to read a random number generator circuit rather than using a complex software routine to generate a random number. Other hardware uses may include random selection of one of several eligible units to execute an instruction, random translation lookaside buffer entry replacement, random branch history buffer or target address buffer replacement in a branch predictor, etc.
The random number generator circuits are typically pseudo-random circuits, in which the circuits attempt to generate a relatively unpredictable sequence of numbers over time (when viewed from the consumer of the numbers) using some sort of deterministic algorithm. However, for brevity herein, these circuits will be referred to as random number generator circuits. Generally, it is desirable that the algorithm produce a long sequence of numbers before any repeated patterns are experienced, either in the values used in the algorithm or in the output random number values. The number of values produced before a repeat is referred to as a harmonic of the random number generator, and producing one or more long sequences (high harmonics) may be referred to as complex harmonics. It may generally be desirable to produce large, odd numbered harmonics, prime number harmonics, etc. to improve the apparent randomness of the generated numbers.
Algorithms having complex harmonics tend to reduce the occurrence of degenerative cases in which the same random number is generated repeatedly over a relatively short period of time, or the same random number is generated with a short, consistent frequency over a short period of time. For example, in the cache replacement scheme mentioned above, if a cache miss in a given set occurs with a frequency that matches a harmonic of the random number generator, then the same way would be replaced in the set each time where it may be desirable, in general, to replace different ways in the set for each miss to replace less recently accessed data in the set with the more recently accessed data. In a simple example, if a miss within a given set occurs every fourth miss (or frequently the fourth miss) during a certain period of time and every fourth value of the random number generator is the same during the period (or mostly the same), then the same way is replaced in that set during the time period.
Generally, the random number generator circuit may produce a random number within a range of integers. For example, a four way set associative cache having random replacement may include a random number generator circuit which produces a way value (an integer in the range from 0 to 3). A three way set associative cache would have a random number generator which produces an integer in the range of 0 to 2. Thus, the range required of a given random number generator circuit may be arbitrary.